第 388 场力扣周赛

K 个不相交子数组的最大能量值

题目

输入长度为 \(n\) 的整数数组 \(nums\) 和正奇数 \(k\)，输出从数组中选择 \(k\) 个不相交的子数组，能够得到的最大得分。\(k\) 个子数组的得分为 \(\sum_{i=1}^{k}(-1)^{i+1}\times sum[i]\times (k-i+1)\)，其中 \(sum[i]\) 表示第 \(i\) 个子数组中元素之和。

数据范围：\(1\leq n\leq 10^{4}\)，\(-10^{9}\leq nums[i]\leq 10^{9}\)，\(1\leq k\leq n\)，\(1\leq n\times k\leq 10^{6}\)。

思路

定义 \(dp[i][r]\) 表示从区间 \([0,r-1]\) 选择 \(i\) 个不相交子数组，能够得到的最大得分。对于元素 \(nums[r-1]\)，我们有选或者不选两种情况，状态转移方程如下：

$$ dp[i][r]=\max(dp[i][r-1],\max_{l=i-1}^{r-1}(dp[i-1][l]+(sum[r]-sum[l])\times (-1)^{i+1}\times (k-i+1))) $$

初始时，对于所有 \(0\leq i\leq n\)，有 \(dp[0][i]=0\)，其他值初始化为负无穷。使用上述转移方程，时间复杂度为 \(O(kn^{2})\)。可以对其变形，将时间复杂度优化为 \(O(kn)\)，详细参见灵神的题解。小羊的题解使用的是另一种做法，似乎更简洁，但是看不太懂啊。

代码

class Solution {
    public long maximumStrength(int[] nums, int k) {
        int n = nums.length;
        long[] sum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }

        long[][] dp = new long[k + 1][n + 1];
        for (int i = 1; i <= k; i++) {
            Arrays.fill(dp[i], Long.MIN_VALUE);
        }

        for (int i = 0; i < k; i++) {
            long max = Long.MIN_VALUE;
            int w = (2 * (i & 1) - 1) * -1 * (k - i);
            for (int r = i; r < n - (k - i - 1); r++) {
                max = Math.max(max, dp[i][r] - sum[r] * w);
                dp[i + 1][r + 1] = Math.max(dp[i + 1][r], sum[r + 1] * w + max);
            }
        }
        return dp[k][n];
    }
}